package sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class MergeSort {

    public static void main(String[] args) {
//        int[] arr = new int[]{8,4,5,7,1,3,6,2};
        int[] arr;
//        arr = new int[]{-9,78,0,23,-567,70};
        arr = new int[8000000];
        for (int i = 0; i < 8000000; i++){
            arr[i] = (int)(Math.random() * 800000);
        }
        int[] temp = new int[arr.length];
        Date date1 = new Date();
        SimpleDateFormat sim = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = sim.format(date1);
        System.out.println("排序前的时间:"+date1Str);
        mergeSort(arr,0,8000000 - 1,temp);
        Date date2 = new Date();
        String date2Str = sim.format(date2);
        System.out.println("排序后的时间:"+date2Str);
    }


    //分+合的方法
    public static void mergeSort(int[] arr,int left, int right, int[] temp){
        if (left < right){
            int mid = (left + right) / 2;
            //向左递归
            mergeSort(arr,left,mid,temp);
            //向右递归
            mergeSort(arr,mid+1,right,temp);
            //每分解一次就合并一次
            merge(arr,left,mid,right,temp);
        }
    }

    //合并的方法

    /**
     *
     * @param arr：需要排序的原始数组
     * @param left：左边初始索引
     * @param mid：中间索引
     * @param right：右边促使数组
     * @param temp ：做中转的数组
     */
    public static void merge(int arr[],int left, int mid,int right,int[] temp){
        int i = left;//初始化i，左边有序序列的初始索引
        int j = mid + 1;//初始化j，右边有序序列的初始索引
        int t = 0;//指向temp数组的当前索引

        //先把左右两边有序的数据按照规则填充到temp数组，直到左右两边的有序序列有一边处理完毕
        while (i <= mid && j <= right){//将继续，如果发现左边的有序序列小于等于右边的当前元素，则将大的元素放入temp中
            if (arr[i] <= arr[j]){
                temp[t] = arr[i];
                t+= 1;//temp的数组要往后移
                i+= 1;//i也要往后移
            }else {
                temp[t] = arr[j];
                t++;//temp的数组要往后移
                j++;//j也要往后移
            }
        }

        //如果把有剩余数据的一方，依此填充到temp中
        while (i <= mid){//说明左边的元素还没遍历完,就全部填充到temp
            temp[t] = arr[i];
            i++;
            t++;
        }

        while (j <= right){//说明左边的元素还没遍历完,就全部填充到temp
            temp[t] = arr[j];
            j+= 1;
            t+= 1;
        }

        //将temp数组的元素拷贝到arr
        //并不是每次拷贝所有
        t = 0;
        int tempLeft = left;//
        while (tempLeft <= right){//判断是否到达数组末尾
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft+= 1;
        }
    }
}
